#ifndef LIST_SQ_H_

#define LIST_SQ_H_

#include <iostream>
#include "status.h"
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
using namespace std;

template<typename T>
class List_Sq
{
private:
	T * elem;
	int length;
	int listsize;
public:
	List_Sq() : length(0), listsize(LIST_INIT_SIZE)
	{
		this->elem = new T[LIST_INIT_SIZE];
	}
	~List_Sq();
	Status InitList();
	Status DestroyList();
	Status ClearList();
	Status ListEmpty() const;
	Status GetElem(int i, T & e) const;
	int LocateElem(const T & e) const;
	Status PriorElem(const T & cur_e, T & pre_e) const;
	Status NextElem(const T & cur_e, T & next_e) const;
	Status ListInsert(int i, const T & e);
	Status ListInsert_st(const T & e);
	Status ListDelete(int i, T & e);
	Status ListTraverse() const;
	Status ListReverse();
};

template<typename T>
List_Sq<T>::~List_Sq()
{
	delete[] this->elem;
	this->length = 0;
	this->listsize = 0;
}

template<typename T>
Status List_Sq<T>::InitList()
{
	this->elem = new T[LIST_INIT_SIZE];
	this->length = 0;
	this->listsize = 0;
}

template<typename T>
Status List_Sq<T>::DestroyList()
{
	delete[] this->elem;
}

template<typename T>
Status List_Sq<T>::ClearList()
{
	this->length = 0;
}

template<typename T>
Status List_Sq<T>::ListEmpty() const
{
	return this->length == 0;
}

template<typename T>
Status List_Sq<T>::GetElem(int i, T & e) const
{
	if (i < 0 || i >= this->length)
		return ERROR;

	e = this->elem[i];
	return OK;
}

template<typename T>
int List_Sq<T>::LocateElem(const T & e) const
{
	for (int i = 0; i < this->length; i++)
		if (e == this->elem[i])
			return i;

	return -1;
}

template<typename T>
Status List_Sq<T>::PriorElem(const T & cur_e, T & pre_e) const
{
	for (int i = 1; i < this->length; i++)
		if (cur_e == this->elem[i])
		{
			pre_e = this->elem[i - 1];
			return OK;
		}

	return ERROR;
}

template<typename T>
Status List_Sq<T>::NextElem(const T & cur_e, T & next_e) const
{
	for (int i = 0; i < this->length - 1; i++)
		if (cur_e == this->elem[i])
		{
			next_e = this->elem[i + 1];
			return OK;
		}

	return ERROR;
}

template<typename T>
Status List_Sq<T>::ListInsert(int index, const T & e)
{
	if (this->length == this->listsize)
	{
		T * newbase = new T[this->listsize + LISTINCREMENT];
		int j = 0;
		for (int i = 0; i < this->length + 1; i++)
		{
			if (index == i)
				newbase[i] = e;
			else
				newbase[i] = this->elem[j++];
		}
		delete[] this->elem;
		this->elem = newbase;
	}
	else
	{
		for (int i = this->length; i > index; i--)
		{
			elem[i] = elem[i - 1];
		}
		elem[index] = e;
	}

	++this->length;
	return OK;
}

template<typename T>
Status List_Sq<T>::ListInsert_st(const T & e)
{
	int index = this->length;
	for (int i = 0; i < this->length; i++)
		if (e < elem[i])
		{
			index = i;
			break;
		}

	if (this->length == this->listsize)
	{
		T * newbase = new[this->listsize + LISTINCREMENT];
		if (newbase == nullptr)
			return OVERFLOW;
		int j = 0;
		for (int i = 0; i < this->length + 1; i++)
		{
			if (index == i)
				newbase[i] = e;
			else
				newbase[i] = this->elem[j++];
		}
		delete[] this->elem;
		this->elem = newbase;
	}
	else
	{
		for (int i = this->length; i > index; i--)
		{
			elem[i] = elem[i - 1];
		}
		elem[index] = e;
	}

	++this->length;
	return OK;
}

template <typename T>
Status List_Sq<T>::ListTraverse() const
{
	if (this->length == 0)
		return ERROR;

	for (int i = 0; i < this->length; i++)
		cout << "index " << i << " : " << this->elem[i];

	return OK;
}

template <typename T>
Status List_sq<T>::ListReverse()
{	
	for(int i = 0, j = this->length - 1; i < this->length / 2; i++, j--)
	{
		T tmp = this->elem[i];
		this->elem[i] = this->elem[j];
		this->elem[j] = tmp;
	}
	
	return OK;
}

#endif